package com.dyw.Day17;



/**
 * @author Devil
 * @create 2022-01-26-21:27
 *
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 *
 * 有效 二叉搜索树定义如下：
 *
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 *
 * 原理: 二叉搜索树的中序遍历是有序
 * 思路:使用递归对树进行中序遍历 过程中使用一个全局节点对中序遍历过程中的上一个节点进行记录 用于比较 如果全程都是有序 那么借助原理我们就可以的出 这是一个二叉搜索树
 */
@SuppressWarnings("all")
public class Demo01 {
    TreeNode prev; //用来记录中序遍历中上一个节点的值
    public boolean isValidBST(TreeNode root) {
        if(root == null){
            return true;
        }
        //访问左子树
        if(!isValidBST(root.left)){
            return false;
        }
        //访问当前节点如果当前节点值小于中序遍历的前一个节点直接返回false
        if(prev!=null&&prev.val>=root.val){
            return false;
        }
        prev = root;
        //访问右子树
        if(!isValidBST(root.right)){
            return false;
        }
        return true;
    }
}
